package huawei.test01;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * 20230410晚华为机考第一题
 * <p>
 * 题目：充电站（回溯）
 *
 * 考试时误以为是01背包问题，实际是回溯
 * <p>
 * 给定一个充电站的最大允许功率maxP，找到充电站内所有设备的任意一种组合，使得这组设备的功率和最接近且不超过整个充电站的最大功率
 * <p>
 * 假设设备总数量为n，每台设备都有自身的功率Pi （1 <= i <= n）
 * <p>
 * 充电站内的某一台设备都有自身的功率，功率不一定相同
 * 找到任意一种组合指的是不限定组内的设备数量，即一组内的设备数量为1到n都可以
 * <p>
 * 如果不存在这样的组，比如当所有设备的功率均大于maxP时，不存在这样的组，返回0
 *
 * 测试用例：输入 4 20 20 50 60 90  输出90
 */
public class t1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(in.nextInt());
        }
        int maxP = in.nextInt();
        List<Integer> filtedList = list.stream().filter(x -> x <= maxP).collect(Collectors.toList());
        int[] ans = new int[]{0};
        resolve(filtedList, ans, 0, 0, maxP);
        System.out.println(ans[0]);
    }

    private static void resolve(List<Integer> filtedList, int[] ans, int curIndex, int curP, int maxP) {
        if (curIndex >= filtedList.size()) {
            if (curP <= maxP && curP > ans[0]) {
                ans[0] = curP;
            }
            return;
        }
        if (curP > maxP) {
            return;
        } else if (curP == maxP) {
            ans[0] = curP;
            return;
        } else if (curP > ans[0]){
            ans[0] = curP;
        }

        // 选择
        curP += filtedList.get(curIndex);
        // 进入下一个
        resolve(filtedList, ans, curIndex + 1, curP, maxP);
        // 撤销选择
        curP -= filtedList.get(curIndex);

        // 不选进入下一个
        resolve(filtedList, ans, curIndex + 1, curP, maxP);
    }
}
